package com.Questions.DP;


/**
 * 回文子串
 */
public class leetcode647 {
    public int countSubstrings(String s) {
        // 回顾第五题 最长回文子串
        // 通过动态规划维护一个 二维数组 判断i到j的字符串是否是回文串
        // 这道题思路是一样的 只不过要返回能构成回文串的个数
        int n=s.length();
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        boolean[][] DP=new boolean[n][n];
        for(int i=0;i<n;++i){
            DP[i][i]=true;
        }
        // 不要直接枚举右区间 应该先枚举长度 保证将初值的横行和纵行都遍历一遍
        for(int L=2;L<=n;++L){
            for(int l=0;l<n;++l){
                int r=l+L-1;
                if(r>n){
                    break;
                }
                if(s.charAt(l)!=s.charAt(r)){
                    DP[l][r]=false;
                }else{
                    if(r-l<3){
                        DP[l][r]=true;
                    }else{
                        DP[l][r]=DP[l+1][r-1];
                    }
                }
            }
        }
        int sum=0;
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(DP[i][j]){
                    sum++;
                }
            }
        }
        return sum;
//        for(int i=0;i<n;++i){
//            for(int j=i+1;j<n;++j){
//                if(s.charAt(i)==s.charAt(j)){
//                    DP[i][j]=DP[i-1][j-1];
//                }else{
//                    DP[i][j]=false;
//                }
//            }
//        }
    }
}
